package com.zhengwl.study.algorithm;

import java.util.HashMap;

public class Sudoku {

	private int[][] array;
	public Sudoku(int[][] temp){
		this.array=temp;
	}
	private HashMap<Integer, Integer> history = new HashMap<>(200);

	public void getResult(int horizontal, int vertical) {
		for (int i = horizontal; i>=0&&i < 9; i++) {
			boolean flag = false;
			if (vertical < 0) {
				flag = true;
				vertical = 0;
			}
			

			for (int j = vertical;j>=0&&j < 9; j++) {
				if (array[i][j] > 0) {
					continue;
				} else {
					if (!setValue(i, j, array)) {
						getResult(i, --j);
					}
				}
			}
			
			if (flag) {
				getResult(--i, vertical);
			}
		}
	}

	public  boolean setValue(int i,int j,int[][] array){
		if(i<0||j<0){
			return false;
		}
		try {
			 for (int v=1;v<10;v++){
		            boolean setSuccess=true;
		            //判断横行
		            for(int ii=i;ii<9;ii++){
		                if(array[ii][j]==v){
		                    setSuccess=false;
		                    break;
		                }
		            }
		            //判断竖行
		            for(int jj=j;jj<9;jj++){
		                if(array[i][jj]==v){
		                    setSuccess=false;
		                    break;
		                }
		            }
		            //判断子区域
		            int iii=(i/3)*3;
		            int jjj=(j/3)*3;
		            for(int subi=iii;subi<iii+3;subi++){
		            	boolean b=false;
		            	for(int subj=jjj;subj<jjj+3;subj++){
		            		 if(array[subi][subj]==v){
		                         setSuccess=false;
		                         b=true;
		                         break;
		                     }
		                }
		            	if(b){
		            		break;
		            	}
		            }
		           
		            //小于等于以前成功设置的值不要
		            //String key=Integer.toString(i)+j;
		            if(history.containsKey(i*10+j)&&v<=history.get(i*10+j)){
		            	continue;
		            }
		            
		            if(setSuccess){
		                array[i][j]=v;
		                //记录下值，便于回溯
		                history.put(i*10+j, v);
		                return  true;
		            }
		            
		        }
		} catch (Exception e) {
			System.out.println("i:"+i+",j:"+j);
			System.exit(-1);
		}
        return  false;
    }
}
